public class Main {
    public static void main(String[] args) {
        System.out.println(new Solution().maxProfit(new int[]{3,3,5,0,0,3,1,4}));
        System.out.println(new Solution().maxProfit(new int[]{1,2,3,4,5}));
        System.out.println(new Solution().maxProfit(new int[]{7,6,4,3,1}));
        System.out.println(new Solution().maxProfit(new int[]{1}));
    }
}


class Solution {
    public int maxProfit(int[] prices) {
        int[] dp1 = new int[prices.length];     //第一笔交易，下表为下标前的最大收益
        int[] dp2 = new int[prices.length];     //第二笔交易，下标为下标及之后的最大收益

        //init dp1
        int min = prices[0];
        for (int i = 1; i < prices.length; i++) {
            dp1[i] = Math.max(prices[i] - min, dp1[i - 1]);
            min = Math.min(min, prices[i]);
        }

        //init dp2
        int max = prices[prices.length - 1];
//        min = prices[prices.length - 1];
        for (int i = prices.length - 2; i >= 0; i--) {
            dp2[i] = Math.max(max - prices[i], dp2[i + 1]);
            max = Math.max(max, prices[i]);
        }

        int maxProf = 0;
        for (int i = 0; i < prices.length; i++) {
            maxProf = Math.max(dp1[i] + dp2[i], maxProf);
        }
        return maxProf;
    }
}